home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 5769 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.4 KB  |  57 lines
  1. Newsgroups: comp.lang.lisp,comp.lang.c++,comp.lang.c,comp.lang.misc,comp.theory
  2. Path: newsfeed.ed.ac.uk!edcogsci!jeff
  3. From: jeff@cogsci.ed.ac.uk (Jeff Dalton)
  4. Subject: Re: allocator studies (was Re: GC & traditional allocators & textbooks)
  5. Message-ID: <DMD9Bx.6qq.0.macbeth@cogsci.ed.ac.uk>
  6. Organization: Centre for Cognitive Science, Edinburgh, UK
  7. References: <4f2ila$6p8@jive.cs.utexas.edu> <823455623snz@wildcard.demon.co.uk> <4f59c3$7il@jive.cs.utexas.edu>
  8. Distribution: inet
  9. Date: Tue, 6 Feb 1996 18:14:21 GMT
  10.  
  11. In article <4f59c3$7il@jive.cs.utexas.edu> wilson@cs.utexas.edu (Paul Wilson) writes:
  12. >In article <823455623snz@wildcard.demon.co.uk>,
  13. >Cyber Surfer  <cyber_surfer@wildcard.demon.co.uk> wrote:
  14. >>In article <4f2ila$6p8@jive.cs.utexas.edu>
  15. >>           wilson@cs.utexas.edu "Paul Wilson" writes:
  16. >>
  17. >>> The history of allocator
  18. >>> research has been a big mess---the literature is a bit of a disaster
  19. >>> area---and the textbooks reflect this.  The analyses in the books are 
  20. >>> shallow and largely wrong.  [...]
  21. >>
  22. >>I won't argue with that! ;-) I'd love to see a good summary.
  23. >
  24. >Well, very briefly:
  25. >
  26. > [...]
  27. >
  28. >   5. The best-known policies (best fit and address-ordered first fit)
  29. >      work better than anyone ever knew, while some policies (Knuth's
  30. >      "Modified First Fit" or "Next Fit") work worse than anyone ever
  31. >      knew, for some programs.  This is because randomized traces tend
  32. >      probabilistically to ensure that certain important realistic
  33. >      program behaviors will never happen in traditional experiments.
  34.  
  35. > [...]
  36.  
  37. >>> "Modified First Fit" with the roving pointer is the clearest example.  It
  38. >>> was a bad idea, and it was quickly shown to be bad, but some other 
  39. >>> textbook writers keep mindlessly cribbing from Knuth, [...]
  40.  
  41. When I was a student, there was a course in which people implemented
  42. various alloc/free policies, to compare them experimentally.  They got
  43. results rather different from the ones suggested by Knuth but were
  44. reluctant to draw the conclusion that Knuth might be wrong.  I'm not
  45. sure how they convinced the instructor that they hadn't blown it.
  46. (I've forgotten the experimental details, I'm afraid.)
  47.  
  48. Anyway, for some reason, I've experienced pretty good performance from
  49. mark-and-sweep GCs, and without much in the way of long pauses, both
  50. with Lisp systems and with implementations of strings.  The really
  51. slow, long pause, GCs I've encountered were copying ones.
  52.  
  53. -- jd
  54.  
  55.  
  56.  
  57.